import java.util.Comparator;
import java.util.PriorityQueue;

/*
题目描述：数据流中的中位数
方法：
使用最大堆最小堆存放数据，两个堆内数字的数量相差不能超过1
可以实现Insert  O(n)
GetMedian     O(1)
 */
public class E41 {
    public static void main(String[] args) {
        Solution41 A = new Solution41();
        int[] num = {5,2,3,4,1,6,7,0,8};
        for(int i = 0; i < num.length; i++){
            A.Insert(num[i]);
            System.out.print(A.GetMedian() +" ");
        }
    }
}

class Solution41 {
    PriorityQueue<Integer> min = new PriorityQueue<>();
    PriorityQueue<Integer> max = new PriorityQueue<>(15, (o1, o2) -> o2.compareTo(o1));
    int count = 0;
    public void Insert(Integer num) {
        if(count % 2 == 0){
            max.offer(num);
            int temp = max.poll();
            min.offer(temp);
        }
        else{
            min.offer(num);
            int temp = min.poll();
            max.offer(temp);
        }
        count ++;
    }

    public Double GetMedian() {
        if(count % 2 == 0){
            return (max.peek() + min.peek()) / 2.0;
        }
        else{
            return (double)min.peek();
        }
    }
}